package algorithm.heap;

import cn.hutool.extra.spring.SpringUtil;
import com.example.hashcode.HashCodeTest;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * 基数排序
 *
 * @author csp 2021-12-05
 */
public class Code05_RadixSort {

    /**
     * 不以比较的排序
     * 1、计数排序
     * 2、基数排序
     */

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }

    public static void radixSort(int[] arr, int L, int R, int digit) {
        //
        final int radix = 10;
        int i = 0, j = 0;
        //
        int[] bucket = new int[R - L + 1];
        for (int d = 1; d <=digit ; d++) {//
            /*
                此题关键
                count 数组记录非数字出现频率，而是累计出现的频率
                count[1] (0,1)出现频率
                count[2] (0-2)...
                count[9] (0-9)...
             */
            int[] count = new int[radix];
            for (i = L; i <= R; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            // 从右往左取出数据，类似一种出栈的效果。后入栈的先出去
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }


    public static int getDigit(int x, int d) {
        // Math.pow 获取数的幂的值。
        return (x / ((int)Math.pow(10, d - 1))) % 10;
    }

    public static void main(String[] args) {
//        System.out.println(Math.pow(10, 2));
        Integer[] arr = {1, 50, 24, 411, 37};
//        radixSort(arr);
//        System.out.println(Arrays.toString(arr));
        Arrays.sort(arr);

//        System.out.println(System.identityHashCode(arr));
//        System.out.println(Arrays.hashCode(arr));
//        Integer a = new Integer(1);
//        Integer b = new Integer(1);
//        Integer c = 200;
//        Integer d = 200;
        String e= "aa111111111111111111";
        String f = new String("aa111111111111111111");
        String g = "aa111111111111111111";
        String h = String.valueOf("aa111111111111111111");

//        System.out.println(System.identityHashCode(a));
//        System.out.println(System.identityHashCode(b));
//        System.out.println(System.identityHashCode(c));
//        System.out.println(System.identityHashCode(d));
        System.out.println(System.identityHashCode(e));
        System.out.println(System.identityHashCode(f));
        System.out.println(System.identityHashCode(g));
        System.out.println(System.identityHashCode(h));
        System.out.println(f == g);
        // 回文链表
    }
}
